package com.sort;

import com.heap.MaxHeap;
import utils.CreateArr;

public class HeapSort {
    //堆排序,将需要排序的数组中的元素全部依次入堆,然后反向的取出最大值.
    // 算法复杂度 O(n * log n)
    public static int[] heapSort_1(int[] arr) {
        MaxHeap maxHeap = new MaxHeap(arr.length);
        for (int anArr : arr) {
            maxHeap.insert(anArr);
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            arr[i] = maxHeap.extrackMax();
        }
        return arr;
    }

    /*优化1:Heapify
    * 最大堆特性:
    *       一个没有子节点的节点,可以看做是只有一个根节点的堆,
    *       arr[count / 2] 即为堆中第一个拥有节点的节点
    * 因此只需要从下向上的,依次执行shiftDown操作,由小的堆逐渐变成大的堆就可以了
    * 算法复杂度 O(n)
    * */
    public static int[] heapSort_2(int[] arr) {
        MaxHeap maxHeap = new MaxHeap(arr);
        //在向 MaxHeap 中传入 arr 数组后,整个数组已经满足最大堆
        for (int i = arr.length - 1; i >= 0; i--) {
            arr[i] = maxHeap.extrackMax();
        }
        return arr;
    }

    /*优化2:原地堆排序
    * 在最大堆中,将第一个位置的值(同时也是最大值)与数组最后一个位置交换位置,在原数组的基础上直接得到有序数组,
    * 而不需要开辟新的数组空间来存储堆中排好序的元素.
    * */
    public static int[] heapSort_3(int[] arr) {
        MaxHeap maxHeap = new MaxHeap(arr);
        return maxHeap.sortInside();
    }


    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int arr[] = heapSort_1(CreateArr.createRandomInt(20, 0, 100));
        long end = System.currentTimeMillis();
        System.out.println("\n" + (end - start));
        System.out.print("\n排序后 : ");
        for (int i : arr) {
            System.out.print(" " + i);
        }
    }


}
